package com.zhugang.week07;

import java.util.PriorityQueue;

/**
 * @program algorithms
 * @description: MedianFinder
 * @author: chanzhugang
 * @create: 2022/08/02 11:13
 */
public class MedianFinder2 {

    PriorityQueue<Integer> minQueue = new PriorityQueue<>((o1, o2) -> o1 - o2);

    PriorityQueue<Integer> maxQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);

    /**
     * 295 数据流的中位数
     * 数据流：动态的，所以需要维护数据的插入和查询都要很高效
     * 大顶堆和小顶堆维护数据，大顶堆的堆顶元素就是中位数
     */
    public MedianFinder2() {

    }

    public void addNum(int num) {
        if (maxQueue.isEmpty() || num < maxQueue.peek()) {
            maxQueue.add(num);
        } else {
            minQueue.add(num);
        }

        while (maxQueue.size() < minQueue.size()) {
            maxQueue.add(minQueue.poll());
        }

        while (minQueue.size() < maxQueue.size() - 1) {
            minQueue.add(maxQueue.poll());
        }
    }

    public double findMedian() {
        if (maxQueue.size() > minQueue.size()) {
            return maxQueue.peek();
        } else {
            return (maxQueue.peek() + minQueue.peek()) / 2f;
        }
    }
}